package 分类.二叉树;

import java.util.HashMap;

public class 从中序与后序遍历序列构造二叉树 {
    HashMap<Integer, Integer> hashMap=new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i=0;i<inorder.length;i++){
            hashMap.put(inorder[i],i);
        }
        return build(postorder,0,postorder.length-1,inorder,0,inorder.length-1);
    }

    TreeNode build(int[] post,int poststart,int postend,int[] in,int instart,int inend){
        if(instart>inend){
            return null;
        }
        int rootval=post[postend];
        int index=hashMap.get(rootval);
        int leftsize=index-instart;

        TreeNode root=new TreeNode(rootval);
        root.left=build(post,poststart,poststart+leftsize-1,in,instart,index-1);
        root.right=build(post,poststart+leftsize,postend-1,in,index+1,inend);
        return root;
    }
}
